#include "global.h"

// useful is an initialized array with length = node count.
// useful[node] = 1 if node is useful.
// useful[node] = 0 if node is maybe_useful (see wikipages for more informations)
#define DEBUG

#define PTL_IGNORE_DEPTH 3
#define PTL_MAXGIFT_DEPTH 10

static struct nodestate{
  int useful;
  int entrypoint;
  int depth;
} *nstates;

static struct ptlareas{
  int entrypoint;
  int depth;
  int maxdepth_node;
} *pareas;

static int ptlnb = 0;

static int is_an_exit(int node, int *exits, int nbexits){
	int i;
	int res = 0;
	for(i = 0; i < nbexits; i++){
		if(exits[i] == node){
			res = 1;
			break;
		}
	}

	return res;
}

static int littleguy(igraph_t *tree, int node, int parent, int *exits, int nbexits){

	igraph_vector_t res;
	igraph_vector_init(&res,1);

	igraph_vs_t vs;
	igraph_vs_1(&vs,node);

	nstates[node].useful = MAYBE_USELESS;

	if(is_an_exit(node, exits, nbexits)){
		// The node is useful.
		nstates[node].useful = USEFUL;
	} else if(igraph_degree(tree,&res, vs, IGRAPH_ALL, 0) == 1){
		nstates[node].useful = MAYBE_USELESS;
		return MAYBE_USELESS;
	}

	igraph_vs_t vs_adj;
	igraph_vit_t iterator;
	int next_node;

	igraph_vs_adj(&vs_adj, node, IGRAPH_ALL);
	igraph_vit_create(tree, vs_adj, &iterator);

	while(!IGRAPH_VIT_END(iterator)){
		next_node = (int) IGRAPH_VIT_GET(iterator);
		if(next_node == parent) {
			IGRAPH_VIT_NEXT(iterator);
			continue;
		}

		if(littleguy(tree, next_node, node, exits, nbexits) == USEFUL){
			nstates[node].useful = USEFUL;
		}

		IGRAPH_VIT_NEXT(iterator);
	}

	igraph_vit_destroy(&iterator);

	return nstates[node].useful;
}

static void propagate_entrypoint_rec(igraph_t *graph, int root, int entry, unsigned char *seen, int nbnodes)
{
	int next_node;
	nstates[root].entrypoint = entry;
	pareas[root].entrypoint = entry;
	seen[root] = 1;

	igraph_vs_t vs_adj;
	igraph_vit_t iterator;

	igraph_vs_adj(&vs_adj, root, IGRAPH_ALL);
	igraph_vit_create(graph, vs_adj, &iterator);

	for(;!IGRAPH_VIT_END(iterator);IGRAPH_VIT_NEXT(iterator)){
		next_node = (int) IGRAPH_VIT_GET(iterator);

		if (!seen[next_node]) {
			if (nstates[next_node].useful == MAYBE_USELESS){
				propagate_entrypoint_rec(graph, next_node, entry, seen, nbnodes);
			}
		}
	}

	igraph_vit_destroy(&iterator);

}

static void propagate_entrypoint(igraph_t *graph, int root)
{
	int nbnodes = igraph_vcount(graph);
	unsigned char seen[nbnodes];
	memset(seen, 0, nbnodes);

	propagate_entrypoint_rec(graph, root, root, seen, nbnodes);
}

static void compute_depth(igraph_t *graph, int root, int depth)
{
	int next_node;

	igraph_vs_t vs_adj;
	igraph_vit_t iterator;

	if (nstates[root].depth < depth)
		return;
	else {
		igraph_vs_adj(&vs_adj, root, IGRAPH_ALL);
		igraph_vit_create(graph, vs_adj, &iterator);

		nstates[root].depth = depth;
		
		if (pareas[nstates[root].entrypoint].depth < depth) {
			pareas[nstates[root].entrypoint].depth = depth;
			pareas[nstates[root].entrypoint].maxdepth_node = root;
		}

		for(;!IGRAPH_VIT_END(iterator);IGRAPH_VIT_NEXT(iterator)){
			next_node = (int) IGRAPH_VIT_GET(iterator);

			if (nstates[next_node].useful == MAYBE_USELESS){
				compute_depth(graph, next_node, depth + 1);
			}
		}

		igraph_vit_destroy(&iterator);
	}
}

static void ptl_addgift(igraph_t *graph)
{
	int i;
	
	for(i = 0; i < ptlnb; i++){
		if(pareas[i].depth > PTL_IGNORE_DEPTH){
			if(pareas[i].depth <= PTL_MAXGIFT_DEPTH){
				igraph_cattribute_VAS_set(graph,"color", pareas[i].maxdepth_node, "olivedrab2");
				dungeonmap_gift(get_roominfo(graph, pareas[i].maxdepth_node));
			}
		}
	}
}

int pointlessareas(igraph_t *graph, int entrance, int *exits, int nbexits)
{
	//http://code.google.com/p/dungeonfd/wiki/PointlessAreaDetection
	// Step 1: create a spanning tree and mark nodes as useful or maybe_useless
	igraph_t tree;
	igraph_minimum_spanning_tree_unweighted(graph,&tree);

	int nbnodes = igraph_vcount(graph);
	int i;
	int next_node;

	nstates = calloc(nbnodes, sizeof(struct nodestate));
	pareas = calloc(nbnodes, sizeof(struct nodestate));
	
	for (i = 0; i < nbnodes; i++) {
		nstates[i].entrypoint = -1;
		pareas[i].entrypoint = -1;
	}

	littleguy(&tree, entrance, -1, exits, nbexits);

	// Step 2: filter false positives
	// Entry point marking
	for (i = 0; i < nbnodes; i++) {
		if (nstates[i].useful != USEFUL)
			continue;

		nstates[i].entrypoint = i;

		propagate_entrypoint(&tree, i);

	}

	// Property propagation
	int changed;

	do {
		changed = 0;

		for (i = 0; i < nbnodes; i++) {
		
			int usefulcount = 0;

			if (nstates[i].useful != MAYBE_USELESS)
				continue;

			igraph_vs_t vs_adj;
			igraph_vit_t iterator;

			igraph_vs_adj(&vs_adj, i, IGRAPH_ALL);
			igraph_vit_create(graph, vs_adj, &iterator);

			while(!IGRAPH_VIT_END(iterator)){
				next_node = (int) IGRAPH_VIT_GET(iterator);

				if (nstates[i].entrypoint != nstates[next_node].entrypoint) {
                                  //nstates[next_node].useful = USEFUL;
                                  nstates[i].useful = USEFUL;
								  propagate_entrypoint(&tree, i);
								  //propagate_entrypoint(&tree, next_node);
                                  changed = 1;
				} else if (nstates[next_node].useful == USEFUL) {
					usefulcount ++;
				}

				IGRAPH_VIT_NEXT(iterator);
			}

			igraph_vit_destroy(&iterator);

			if (usefulcount >= 2) {
				nstates[i].useful = USEFUL;
				propagate_entrypoint(&tree, i);
				changed = 1;
			}

		}

	} while (changed);

	// Depth computation
	// Initialize depths
	for (i = 0; i < nbnodes; i++)
		nstates[i].depth = 100000;

	for (i = 0; i < nbnodes; i++) {
		if (nstates[i].useful != USEFUL)
			continue;

		compute_depth(&dungeon_graph, i, 0);
	}

	int uselesscount[total_rooms];
	int depthcount[total_rooms];
	int maxdepthnode[total_rooms];
	memset(uselesscount, 0, sizeof(int) * total_rooms);
    memset(depthcount, 0, sizeof(int) * total_rooms);
	memset(maxdepthnode, 0, sizeof(int) * total_rooms);

	for (i = 0; i < nbnodes; i++) {
		if (nstates[i].useful == MAYBE_USELESS)
			nstates[i].useful = USELESS;

		if (nstates[i].useful == USELESS) {
			uselesscount[nstates[i].entrypoint] ++;

			if (depthcount[nstates[i].entrypoint] < nstates[i].depth) {
				depthcount[nstates[i].entrypoint] = nstates[i].depth;
				maxdepthnode[nstates[i].entrypoint] = i;
			}
		}
#ifdef DEBUG
		printf("node %d: %s entry point %d, depth %d\n", i, nstates[i].useful == USEFUL ? "useful" : nstates[i].useful == MAYBE_USELESS ? "maybe useless" : "useless", nstates[i].entrypoint, nstates[i].depth);
#endif
	}

    for (i = 0; i < total_rooms; i++) {
		if (uselesscount[i] != 0) {
			pareas[ptlnb].entrypoint = i;
			pareas[ptlnb].depth = depthcount[i];
			pareas[ptlnb].maxdepth_node = maxdepthnode[i];
			ptlnb++;
		}	
	}

	for (i = 0; i < ptlnb; i++) {
		printf("area %d entry point %d depth %d maxdepthnode %d\n", i, pareas[i].entrypoint, pareas[i].depth, pareas[i].maxdepth_node);
	}

	ptl_addgift(&dungeon_graph);
	free(nstates);
	free(pareas);
	nstates = NULL;
	pareas = NULL;

	igraph_destroy(&tree);

	return 0;
}


